import random
import numpy as np
import copy
import matplotlib.pyplot as plt
import pandas as pd


class Node():
    def __init__(self):
        self.Num = 0
        self.Name = None
        self.Longitude = 0
        self.Latitude = 0
        self.Demand = 0
        self.Fixed_Cost = 0

class Model():
    def __init__(self):
        self.I = []
        self.J = []
        self.node_num = 0
        self.cost = {}
        self.distance = {}

        self.x = []
        self.y = []
        self.z = 0


def Node_information(node):
    print('-----')
    print('node_num:',node.Num)
    print('node_name:',node.Name)
    print('node.Latitude:',node.Latitude)
    print('node.Longitude:',node.Longitude)
    print('node.Demand:',node.Demand) # h
    print('node.Fixed_Cost:',node.Fixed_Cost)

def ReadData(filepath_1,filepath_2,model):
    df_1 = pd.read_excel(filepath_1)
    for i in range(0,df_1.shape[0]):
        node = Node()
        node.Num = i
        node.Name = df_1['Name'][i]
        node.Longitude = df_1['Longitude'][i]
        node.Latitude = df_1['Latitude'][i]
        # node.Longitude = df_1['Latitude'][i]
        # node.Latitude = df_1['Longitude'][i]
        node.Demand = df_1['Demand'][i]
        node.Fixed_Cost = df_1['Fixed_Cost'][i]
        model.I.append(node)
        model.J.append(node)
        model.node_num = model.node_num + 1

    # for node in model.I:
    #     Node_information(node)

    df_2 = pd.read_excel(filepath_2)
    for i in range(0,df_2.shape[0]):
        for j in range(i,df_2.shape[0]):
            model.cost[i,j] = df_2[i][j]
            model.distance[i,j] = model.cost[i,j]*2
            model.cost[j,i] = model.cost[i,j]
            model.distance[j,i] = model.distance[i,j]

def Initialize(model,node_num):
    # 好像也用不上了
    model.z = float('inf')
    for i in range(node_num):
        model.x.append(0)
        model.y.append([])
        for j in range(node_num):
            model.y[i].append(0)

def Greedy_UFLP(model):
    improve_condition = True
    cnt = 0
    while(improve_condition == True):
        improve_condition = False
        # a = time.time()
        z_k = None
        best_z = model.z
        print('第{}次迭代，系统最优值为{}'.format(cnt,best_z))
        for k in range(model.node_num):
            if(model.x[k] == 0):
                # print('==================正在遍历第{}个节点==================='.format(k))
                x_temp_k = copy.deepcopy(model.x)
                y_temp_k = copy.deepcopy(model.y)
                # 不能直接copy！！！！要把之前为1的工厂关掉！！！！！
                x_temp_k[k] = 1 
                open_list = []
                for i in range(len(x_temp_k)):
                    if (x_temp_k[i] == 1):
                        open_list.append(i)
                # print('本次尝试中开了工厂{}'.format(open_list))
                # print('当前k = {},x_temp_k[k] = {}'.format(k,x_temp_k[k]))
                # 在当前解的基础上尝试打开工厂k
                for i in range(model.node_num):
                    nearest_cost = float('inf')
                    for j in range(model.node_num):
                        # 遍历当前解中所有开设的工厂
                        if( x_temp_k[j] == 1 and model.cost[i,j] < nearest_cost ):
                            nearest_node = j
                            nearest_cost = model.cost[i,j]
                        elif(y_temp_k[i][j] == 1):
                            y_temp_k[i][j] = 0
                    y_temp_k[i][nearest_node] = 1
                    # print('将客户{}分配给工厂{}'.format(i,nearest_node))
                z_k = 0
                sum_1 = 0
                sum_2 = 0
                for j in range(len(model.J)):
                    sum_1 = sum_1 + model.J[j].Fixed_Cost * x_temp_k[j]
                for i in range(len(model.I)):
                    for j in range(len(model.J)):
                        # if(y_temp_k[i][j] == 1):
                            # print('将客户{}分配给工厂{}'.format(i,j))
                        sum_2 = sum_2 + model.I[i].Demand * model.cost[i,j]*y_temp_k[i][j]
                z_k = (sum_1 + sum_2)
                # print('开设工厂{}的时候，系统最优成本是{}'.format(k,z_k))
                # print(z_k)
                # 记录当前开设工厂k的成本
                # 找出挨个开设工厂k后的最低成本
                if(z_k < best_z):
                    # print('更新系统最优解')
                    best_z = z_k
                    record_x = copy.deepcopy(x_temp_k)
                    record_y = copy.deepcopy(y_temp_k)
                    improve_condition = True
            else:
                continue
        model.x = copy.deepcopy(record_x)
        open_list = []
        for i in range(len(model.x)):
            if (model.x[i] == 1):
                open_list.append(i)
        print('第{}次循环中开了工厂{}'.format(cnt,open_list))
        model.y = copy.deepcopy(record_y)
        model.z = best_z
        cnt = cnt + 1

    return model.x,model.y,model.z


def Swap_UFLP(model,x,y,z):
    improve_condition = True
    while (improve_condition == True):
        improve_condition = False
        best_z = z
        for j in range(len(x)):
            # 遍历所有设施
            if (x[j] == 1):
                # 如果设施j开放
                for k in range(len(x)):
                    if (x[k] == 0):
                        # 打开关闭的设施，关闭打开的设施
                        temp_x = copy.deepcopy(x)
                        # temp_x是交换后的x，temp_y是交换后得到的y
                        temp_x[k] = 1
                        temp_x[j] = 0
                        temp_y = copy.deepcopy(y)
                        for i in range(len(model.I)):
                            nearest_cost = float('inf')
                            for p in range(len(model.J)):
                                if (temp_x[p] == 1 and model.cost[i,p] < nearest_cost ):
                                    nearest_cost = model.cost[i,p]
                                    nearest_node = p
                                elif(temp_y[i][j] == 1):
                                    temp_y[i][j] = 0
                            temp_y[i][nearest_node] = 1
                        z_k = 0
                        sum_2 = 0
                        for i in range(len(model.I)):
                            for j in range(len(model.J)):
                                sum_2 = sum_2 + model.I[i].Demand * model.cost[i,j]*temp_y[i][j]
                        z_k =  sum_2
                        if(z_k < best_z):
                            # print('更新系统最优解')
                            best_z = z_k
                            record_x = copy.deepcopy(temp_x)
                            record_y = copy.deepcopy(temp_y)
                            improve_condition = True
                    else:
                        continue
            else:
                continue               
        x = copy.deepcopy(record_x)
        y = copy.deepcopy(record_y)
        z = copy.deepcopy(best_z)
        # print(z)


    return x,y,z


def Show_Picture(model):
    def randomcolor():
        colorArr = ['1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
        color = ""
        for i in range(6):
            color += colorArr[random.randint(0,14)]
        return "#"+color

    plt.figure(figsize=(15,10))
    plt.title('UFLP')
    for i in range(len(model.I)):
        for j in range(len(model.J)):
            if (model.y[i][j] != 0):
                color_generate = randomcolor()
                x = [ model.I[i].Latitude ,model.I[j].Latitude ] 
                y = [ model.I[i].Longitude ,model.I[j].Longitude ]
                plt.plot(x,y,color = color_generate,linewidth = 3) 

    plt.legend(loc = 0,ncol = 1)

    plt.show()




if __name__ == '__main__':
    filepath_1 = r'88node_Node.xlsx'
    filepath_2 = r'88node_Cost.xlsx'
    model = Model()
    ReadData(filepath_1,filepath_2,model)
    Initialize(model,model.node_num)
    model.x,model.y,model.z = Greedy_UFLP(model)
    print('========GREEDY最优解：{}========'.format(model.z))
    x,y,z = Swap_UFLP(model,model.x,model.y,model.z)
    model.x = copy.deepcopy(x)
    model.y = copy.deepcopy(y)
    model.z = copy.deepcopy(z)
    print('========SWAP最优解：{}========'.format(model.z))
    Show_Picture(model)